package query;


//        二分查找的前提条件是有序数列，普通查找则不需要。
//        查找到返回该元素的下标，否则返回-1。
//        普通查找的时间复杂度为O(N), 二分查找的时间复杂度为O(logN)。
//        2^m=N(m为折半查找的次数)，那么m=log(N)，二分查找的时间复杂度就为O(logN)。
//        寻找左侧边界的二分查找[1,2,2,2,3,4,5],这里期望返回第四个2的索引。
//
public class BinarySearch4 {

    public static int binarySearch3(int[] list, int key)
    {
        int low = 0;
        int high = list.length-1;
        while (low <= high)   //寻找左侧边界的二分查找[1,2,2,2,3,4,5],这里期望返回第四个2的索引。
        {
            //int mid = (low + high) / 2;// 这里可能因为数据溢出，所以优化
            int mid = low + (high - low) / 2;
            if (key < list[mid])
            {
                high = mid-1; //寻找左侧边界的二分查找[1,2,2,2,3,4,5],这里期望返回第四个2的索引。
            }
            else if (key > list[mid])
            {
                low = mid + 1;
            }
            else if (key == list[mid]){
                low = mid + 1;
            }

        }
        return list[low-1] == key ? low-1 : -1;
    }


    public static void main(String[] args) {
        int[] list = new int[]{1, 2, 2, 2, 3, 4, 5};
        System.out.println(binarySearch3(list, 2));
    }
}
